#pragma once

#include "ezstl_deque.hpp"
#include "ezstl_heap.hpp"
#include "ezstl_vector.hpp"

namespace ezstl {

template <typename T, typename Sequence = ezstl::Deque<T>>
class Queue {
 public:
  using value_type = typename Sequence::value_type;
  using size_type = typename Sequence::size_type;
  using reference = typename Sequence::reference;
  using const_reference = typename Sequence::const_reference;

 protected:
  Sequence c;

 public:
  Queue() : c{} {}
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  void push(const_reference value) { c.push_back(value); }
  void pop() { c.pop_front(); }
};

template <typename T, typename Sequence = ezstl::Vector<T>,
          typename Compare = std::less<typename Sequence::value_type>>
class Priority_queue {
 public:
  using value_type = typename Sequence::value_type;
  using size_type = typename Sequence::size_type;
  using reference = typename Sequence::reference;
  using const_reference = typename Sequence::const_reference;

 protected:
  Sequence c;
  Compare comp;

 public:
  Priority_queue() : c{} {}
  explicit Priority_queue(const Compare &comp) : c{}, comp(comp) {}
  template <typename InputIterator>
  Priority_queue(InputIterator first, InputIterator last, const Compare &comp)
      : c{first, last}, comp(comp) {
    ezstl::make_heap(c.begin(), c.eng(), this->comp);
  }
  template <typename InputIterator>
  Priority_queue(InputIterator first, InputIterator last) : c{first, last} {
    ezstl::make_heap(c.begin(), c.end(), this->comp);
  }

  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  const_reference top() const { return c.front(); }
  void push(const_reference value) {
    try {
      c.push_back(value);
      ezstl::push_heap(c.begin(), c.eng());
    } catch (...) {
      c.clear();
      throw;
    }
  }
  void pop() {
    try {
      ezstl::pop_heap(c.begin(), c.end());
      c.pop_back();
    } catch (...) {
      c.clear();
      throw;
    }
  }
};

}  // namespace ezstl